In many technical fields and in research, measurements are obtained as a function of various parameter values. In this context, individual, a plurality or all of the parameters on which the measurement value depends are varied in succession, and the average measurement value is determined as a function of the respective set of parameters. So as not to allow the measurement period to increase excessively, some parameters—in particular the parameters which only have a slight influence and/or are irrelevant in the respective field of application—are kept at a fixed value and not varied. If for example n parameters are varied, an n-dimensional value matrix is obtained. In this context, each determined measurement value is stored in the respective matrix element.
So as to be able to set up analytical and/or numerical models using the (raw) measurement values obtained in this manner or to be able to put in place further calculations, it is generally necessary initially to convert these (raw) data into a different format. A conversion which is often used in this connection involves determining boundary contours (in two dimensions a boundary line, in three dimensions a boundary surface) which form a boundary between measurement values below a particular value and measurement values above this particular measurement value.
A particularly clear application for determining boundaries of this type, which is commonly made use of in practice, occurs in relation to image data which are obtained for example by tomography methods (although the type of image generation is irrelevant; for example, image values may be obtained using X-rays, nuclear spin methods or ultrasound methods). Tomography methods of this type are used in a wide range of technical fields.
Perhaps the best known and most widespread application for this is in the field of medical technology. In this context, the measurement values obtained represent particular material properties (especially tissue properties), such as the density of the tissue. In this context, the measurement values are typically obtained in three dimensions. The data can subsequently be represented for example in the form of greyscale representations. Using greyscale representations of this type, it is possible for example to distinguish different tissue regions from one another (for example organs, bones, cysts, tumours, air-filled cavities and the like). However, if the data obtained are in particular to undergo further automated processing and/or be used for purposes other than simple observation, it is often necessary to carry out automated calculation of the boundary surfaces (in the case of three-dimensional data), with as little user intervention as possible.
In the prior art, what is known as the “marching cubes algorithm”, developed in the mid-eighties by W. E. Lorensen and H. E. Cline, is made use of for this purpose (see W. E. Lorensen and H. E. Cline, “Marching Cubes; A High Resolution ED Surface Construction Algorithm”, Comput. Graph. Vol. 21 (1987), pages 163-169). This algorithm involves successive migration through the three-dimensional grid. If the algorithm establishes that for two mutually adjacent 3D grid points the respective measurement value is above the boundary value in one case and below the boundary value in one case, the algorithm concludes from this that a boundary surface should be arranged here. This determination, as to whether and if applicable where a boundary surface should be arranged, is carried out from a (varying) central grid point in relation to all of the surrounding grid points. With the “collected” knowledge as to in which corner regions or edge regions a boundary surface is to be arranged, the most suitable base boundary surface arrangement (in other words the most suitable “template”) is selected from a set of base boundary surface arrangements (known as “templates”). This check is carried out for all of the grid points in succession. Subsequently, the base boundary surface arrangements determined in this manner are interconnected to give complete boundary surfaces.
Even though the “marching cubes” algorithm often determines helpful boundary surfaces in practice, there are noticeable and significant problems with it. A first problem involves selecting the set of “templates”. If this set is selected to be too large, the algorithm generally requires too much calculating time. Moreover, template sets of this type rapidly become confusing, and templates are therefore easily “forgotten”. A further problem with the “marching cubes” algorithm is that the surfaces obtained are generally not clear-cut and moreover often have holes—that is to say are not completely closed. This can in some cases lead to major problems in the further processing of the boundary surface data. This problem occurs in particular if a comparatively small number of base surface arrangements (templates) are used (for example for reasons of calculating time).
Even though it may still appear possible to implement and use a complete set of base surface arrangements for a program of this type for three-dimensional data, major problems are encountered as soon as four-dimensional data are involved (for example 3D data which vary over time). Accordingly, the “marching cubes” approach cannot de facto be generalised to general n-dimensional problems where n≧4 (or only with great difficulty).
So as to reduce (and ideally to prevent) the above-disclosed problems involving non-closed surfaces, a wide range of proposals for modifying the basic “marching cubes” algorithm have already been proposed. A summary of previous approaches may be found for example in the scientific publication “A Survey of the Marching Cubes Algorithm” by T. S. Newman and H. Yi in Computers & Graphics, Vol. 30 (2006), pages 854-879. Improvements to the “marching cubes” algorithm have been disclosed in the patent literature too, for example in U.S. Pat. No. 7,538,764 B2. Even though the improvements disclosed in the prior art to the original “marching cubes” algorithm provide considerable improvements, they generally still have drawbacks, in some cases serious drawbacks. In particular, in the algorithms known in the art, the problem of non-closed boundary surfaces is generally still present, in particular when there are particularly unfavourable measurement value distributions.